Wymiar Wapnika-Czerwonienkisa

Wymiar Wapnika-Czerwonienkisa (wymiar VC, ang. VC dimension) – podstawowe pojęcie teorii uczenia maszynowego wprowadzone przez Władimira Wapnika i Aleksieja Czerwonienkisa. Stanowi miarę mocy wyrażania pojęć danej przestrzeni hipotez. Jest on zdefiniowany jako liczność największego zbioru, który jest rozbijany przez przestrzeń hipotez. Fundamentalne twierdzenie teorii uczenia charakteryzuje potencjalnie wyuczalne przestrzenie hipotez jako te o skończonym wymiarze VC.

Rozbijanie

Zbiór przykładów $X$ (o $n$ elementach) jest rozbijany przez przestrzeń hipotez $H,$ jeśli dla dowolnej (z $2^{n}$ możliwych) klasyfikacji elementów zbioru istnieje hipoteza $h\in H,$ dla której $(h(x_{1}),\dots ,h(x_{n})))$ jest taką klasyfikacją. Na przykład dla perceptronu każde trzy niewspółliniowe punkty mogą być rozbite (przykłady pozytywne oddzielone od negatywnych prostą), ale nie istnieją cztery punkty, które są rozbijane. Zatem wymiar VC perceptronu wynosi 3.

3 punkty rozbijane			4 punkty nierozbijalne

Przykłady

• Dla skończonej przestrzeni hipotez wymiar VC nie przekracza logarytmu z liczności.
• Przestrzeń przedziałów ma wymiar 2.
• Przestrzeń sum skończonej liczby rozłącznych przedziałów ma nieskończony wymiar VC.

Bibliografia

• Martin Anthony, Norman Biggs, Computational Learning Theory, Cambridge University Press, 1992.